<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /**
         * 打家劫舍II题：
         * 输入：nums = [1,2,3,1]
         * 输出：4
         * 解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。偷窃到的最高金额 = 1 + 3 = 4 。
         * 偷窃到的最高金额 = 1 + 3 = 4 。 
         * 
         * 思路：这个II和I的唯一区别：首位连接成环，首尾不能同时去打劫，
         * 在选第6的时候，不能光考虑dp[5]或者dp[4]了，还要看dp[0]是否已经选了
        */
        /* 
            时间：O(2 ^ n)
            空间：O(n)
        */

        var rob = function(nums) {
            let len = nums.length
            if (len === 1) {
                return nums[0]
            } else if (len === 0) {
                return 0
            }
            function backTrack (index, sum, end, max) {
                // 退出条件
                if (index >= end) {
                    return Math.max(max, sum)
                }
                // 偷当前房子
                let result1 = backTrack(index + 2, sum + nums[index], end, max)
                // 不偷当前房子
                let result2 = backTrack(index + 1, sum, end, max)
                // 存储结果到缓存
                return Math.max(result1, result2)
            }
            let res1 = backTrack(0, 0, len - 1, 0)
            let res2 = backTrack(1, 0, len, 0)
            return Math.max(res1, res2)
        };
        // console.log(rob([2,7,9,3,1]));
        // console.log(rob([1,2,3,1]));
        // console.log(rob([1, 2])); // 出错1，
        // console.log(rob([1, 3, 1])); // 出错2
        // console.log(rob([2,1,1,2])) // 出错3
        // console.log(rob([1])) // 出错3
        console.log(rob([1, 2, 3])) // 出错3
        
    </script>
</body>

</html>